Batch scheduling with step‐deteriorating processing times to minimize flowtime

Both topics of batch scheduling and of scheduling deteriorating jobs have been very popular among researchers in the last two decades. In this article, we study a model combining these two topics. We consider a classical batch scheduling model with unit‐jobs and batch‐independent setup times, and a model of step‐deterioration of processing times. The objective function is minimum flowtime. The optimal solution of the relaxed version (allowing non‐integer batch sizes) is shown to have a unique structure consisting of two consecutive decreasing arithmetic sequences of batch sizes. We also introduce a simple and efficient rounding procedure that guarantees integer batch sizes. The entire solution procedure requires an effort of O(n) (where nis the number of jobs.) © 2012 Wiley Periodicals, Inc. Naval Research Logistics, 2012     

想定驱动的仿真资源发现方法

为解决在云间共享架构的仿真环境下资源的自动发现问题,研究了仿真资源请求的描述方法及相应的资源发现算法,提出了想定驱动的仿真资源发现方法.方法通过扩展的军事想定描述语言表示仿真资源请求,使用双映射三过滤算法实现仿真资源的自动发现.分析表明,仿真想定驱动的资源发现方法可以实现在云间共享架构下仿真运行所需的大量资源的自动发现,并对发现结果具有语用校验功能,对于仿真环境的快速部署具有积极意义.     

维修任务调度的多目标决策模型

通过对维修调度问题进行分析,考虑到战斗力相关的多种目标因素,针对目前研究的目标单一,又未考虑武器的先进程度、配置等缺陷,就修复后的加权作战时间和装备尽可能少的延误数量双重目标加以研究,并给出了调度算法。从而弥补了这些缺陷,使调度更加合理。最后,算例表明模型的求解方法简单,计算时间较短,可有效地实现维修任务调度。     

A branch‐and‐price algorithm for parallel machine scheduling with time windows and job priorities

This paper presents a branch‐and‐price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of ρ priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has “infinitely” more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two‐cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100‐job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

联合作战规划中资源调度算法研究

以联合作战为例建立任务和作战平台资源模型,通过多维动态列表规划算法(Multidimensional Dynamic List Scheduling,MDLS)进行任务-平台分配,对平台选择提出了两种不同的优先权计算方法,通过对案例求解比较了不同方法的结果.     

作战指挥工作流程建模方法

针对作战指挥工作流程的建模与仿真研究较少的现状,采用了基于高级Petri网的建模方法。首先在企业相关概念定义基础上,对建模对象———作战指挥工作流程进行了定义,简要介绍了Petri网建模方法的特点以及对基本Petri网的扩展,举例说明了4种过程机制映射到Petri网上的方法,提出结合树状组织结构图和资源管理表的方法扩展Petri网库所容量的含义及管理机制。     

一种航天侦察任务-资源匹配的负载均衡方法

当前航天侦察任务预处理方法一般仅从任务需求的角度考虑资源分配问题,容易导致负载不均衡,对此提出了一种综合考虑任务需求与资源负载的任务-资源匹配方法.分析了资源负载均衡需要考虑的任务要素以及相应的描述方法,提出用任务执行概率度量卫星资源负载状况,基于任务流模型给出了单任务执行概率的估算公式,并给出了一种简易的多任务执行概...     

Opportunistic retooling of a flexible machine subject to failure

A set of jobs can be processed without interruption by a flexible machine only if the set of tools required by all jobs can be loaded in the tool magazine. However, in practice the total number of tools required by a job set would exceed the tool magazine capacity. In such situations, the job set has to be carefully partitioned at the start of the production run such that each partition can be processed without interruption. During the production run, if there are unscheduled machine downtimes due to machine failure, this provides an additional opportunity to optimally retool the magazine for a smaller job set consisting of just the unprocessed jobs. In this paper, we study job sequencing rules that allow us to minimize the total expected cost of machine down time due to machine failures and magazine retooling, assuming a dynamic re‐sequencing of the unprocessed jobs after each machine failure. Using these rules, we develop a branch‐and‐bound heuristic that allows us to solve problems of reasonable size. © 2001 John Wiley & Sons, Inc. Naval Research Logistics 48: 79–97, 2001     

基于SWE的空天资源对地观测协同任务规划服务模型

空天协同对地观测是对地观测领域的新趋势。为解决现有空天资源规划调度系统相对独立、协同困难的问题,分析总结了SWE(Sensor Web Enablement)标准,并在此基础上提出了空天资源对地观测协同任务规划服务模型。在此模型中,为实现观测资源共享,建立了空天观测资源传感器描述模型,能够描述典型空天资源的载荷平台、观测机理、定位信息、使用约束和工作特性等信息;为简化观测请求交互流程,基于SOA技术对SWE标准操作进行封装及简化,用户可以在不了解观测平台细节信息的情况下提交观测数据请求。为验证模型有效性,构建了空天资源对地观测协同任务规划实验平台,结果表明该模型具有较强的可实现性和适应性。     

Case‐based reasoning and improved adaptive search for project scheduling

Most scheduling problems are notoriously intractable, so the majority of algorithms for them are heuristic in nature. Priority rule‐based methods still constitute the most important class of these heuristics. Of these, in turn, parametrized biased random sampling methods have attracted particular interest, due to the fact that they outperform all other priority rule‐based methods known. Yet, even the “best” such algorithms are unable to relate to the full range of instances of a problem: Usually there will exist instances on which other algorithms do better. We maintain that asking for the one best algorithm for a problem may be asking too much. The recently proposed concept of control schemes, which refers to algorithmic schemes allowing to steer parametrized algorithms, opens up ways to refine existing algorithms in this regard and improve their effectiveness considerably. We extend this approach by integrating heuristics and case‐based reasoning (CBR), an approach that has been successfully used in artificial intelligence applications. Using the resource‐constrained project scheduling problem as a vehicle, we describe how to devise such a CBR system, systematically analyzing the effect of several criteria on algorithmic performance. Extensive computational results validate the efficacy of our approach and reveal a performance similar or close to state‐of‐the‐art heuristics. In addition, the analysis undertaken provides new insight into the behaviour of a wide class of scheduling heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 201–222, 2000